1. Field of the Invention
The present invention relates to a halftoning operation that converts an input pixel image into a binary image, and more particularly, to an error diffusion processing method that improves an image quality by influencing an error value between a grayscale level of an input pixel and a binary result thereof to neighboring pixels that are to be processed.
2. Description of the Related Art
Generally, binary output devices, such as digital printers, copiers and binary outputting Liquid Crystal Devices (LCDs), deliver chromatic images in black and white. The black and white digital printer, for example, prints an image of various degrees of brightness on a monitor with just two values, i.e., black and white. In order to print the black and white image of various degrees of brightness in the monitor onto a paper, the printer or a personal computer (PC) performs a series of operations to convert an input image into a binary image.
That is, the printer converts the color of each pixel into an image of grayscale level ranging from 0 to 255, and then converts the grayscale image into the binary image. The image of brightness within 0 (Black)˜255 (White) is called the grayscale image, and the operation of converting the grayscale image into the binary image is called ‘halftoning.’ There are various methods of halftoning including an error diffusion processing method.
FIG. 1 shows a conventional binary output device with an error diffusion processing method suggested by Messrs. Floyd and Steinberg. In FIG. 1, ‘x(m, n)’ denotes an input pixel of a grayscale image (“a grayscale level of the input image”), and ‘b(m, n)’ is a binary result of the input pixel. The reference ‘e(m, n)’ denotes an error value, which is a difference between the grayscale level ‘x(m, n)’ and the binary result of the input pixel ‘b(m, n),’ and ‘u(m, n)’ is a corrected grayscale level that is obtained by converting an input pixel value based on the error value ‘e(m, n).’
The error value ‘e(m, n)’ is diffused to neighboring pixels according to an error diffusion coefficient ‘w(k, l)’ of the input pixel value, and the converted grayscale level ‘u(m, n)’ is compared with a fixed threshold ‘T’ to be determined as a binary value of either black or white. More specifically, where the corrected grayscale level ‘u(m, n)’ is greater than the threshold ‘T,’ a white dot is generated. A black dot is generated where the corrected grayscale ‘u(m, n)’ is less than the threshold ‘T.’ As all of the pixels undergo the above operation, the input grayscale image is converted into the binary image. The error diffusion value ‘u(m,n)’ is obtained by the following equation 1:
                              u          ⁡                      (                          m              ,              n                        )                          =                              x            ⁡                          (                              m                ,                n                            )                                +                                    ∑                                                (                                      k                    ,                    l                                    )                                ∈                R                                      ⁢                                                  ⁢                                          W                ⁡                                  (                                                            m                      -                      k                                        ,                                          n                      -                      1                                                        )                                            ⁢                              e                ⁡                                  (                                      m                    ,                    n                                    )                                                                                        <                  Equation          ⁢                                          ⁢          1                >            
where ‘W(m−k, n−1)’ is a set of neighboring pixels for error diffusion, the e(m, n)=u(m,n)−b(m, n), and the ‘b(m, n)’ is ‘255’ if the ‘u(m, n)’ is above the threshold ‘T,’ while it becomes ‘0’ in the other cases.
The above Floyd-Steinberg error diffusion processing method, however, has visual artifacts due to uneven distribution of dots in a region where black dots or white dots have to be clearly shown. Two suggestions were made to overcome the problem of the Floyd-Steinberg error diffusion processing method. One is to re-define the error diffusion coefficient ‘w(m, n),’ and the other is to change the fixed value of the binary threshold ‘T.’
Re-defining the error diffusion coefficient ‘w(m, n)’ achieves some reduction of the visual artifacts as the error diffusion coefficient ‘w(m, n)’ is increased. However, as the error diffusion coefficient increases ‘w(m, n),’ more memory is required to binarize the image, and more computation time is required.
A method of changing a binary threshold can be found in an error distribution through the binary threshold conversion in Eschbach (U.S. Pat. No. 5,535,109), and a roadmap using the method disclosed in Marcu (U.S. Pat. No. 6,160,921), the disclosures of which are incorporated herein by reference.
Similar to the operation of changing grayscale levels of neighboring pixels by diffusing a binary error value to the neighboring pixels, Eschbach diffuses a function of a trace of binarization to neighboring pixels, and converts a binary threshold in the binarization of the neighboring pixels. For an even distribution of black dots or white dots, the binary threshold is adjusted so as to have the neighboring pixels generate a black dot or a white dot according to a grayscale level of an input pixel and the result of the binarization.
Eschbach '109 generates a binarized image of the black dots or the white dots that is more evenly distributed than the Floyd-Steinberg error diffusion processing method. However, the problem of Eschbach is that it has a blank region, in which the black dots are not shown, at the borderline of a bright region of the binarized image. Also, due to a complicated computational operation for obtaining the binary threshold, the processing speed is decreased.
Meanwhile, Marcu '921 binarizes an input image of a grayscale level by using two methods. That is, after setting a range of the grayscale levels for regions where the even distribution of dots is critical, e.g., in a bright grayscale region and a dark grayscale region, an input pixel having the grayscale level within the set range undergoes the binarization by using a roadmap. For the input pixel of an intermediate grayscale level, the Floyd-Steinberg error diffusion processing method is applied. In other words, according to Marcu '921, after determining the relative positions of the a black or white dots according to the brightness of the input image (for an even distribution), a binarization into black or white dot is carried out according to a predetermined relative position without referring to a binary threshold. Accordingly, Marcu '921 requires more memory to store the positions of the black and white dots for determining the relative positions of the black and white dots.
Although the error diffusion processing methods of Eschbach '109 and Marcu '921 have relatively more even distribution of the black dots and the white dots in the bright and dark regions, they cannot improve the print quality of a printout since these methods cannot solve the problem of annoying patterns being generated in the intermediate grayscale region of the input image.
To solve the above problems, Kang et al. (Korean Patent No. 99-53325), the disclosure of which is incorporated herein by reference, suggests an error diffusion processing method using a distance restriction that is capable of reducing the annoying patterns in bright and dark regions, and even in an intermediate grayscale level region. The error diffusion processing method, using the distance restriction, presets an ideal distance between black dots in the bright region and between white dots in the dark region, and adjusts a threshold to maintain the actual distance measured between the black dots and the white dots at the ideal distance.
However, the error diffusion processing method using the distance restriction cannot match the actual distance to the ideal distance due to the location of the dots in a binary output in a cross pattern. Accordingly, even though there are some improvements over the error diffusion processing methods of Floyd-Steinberg, Eschbach '109 and Marcu '921, in terms of the image quality, the annoying patterns are still present in certain regions.
Furthermore, a binary output device, for example, an inkjet printer, is designed to print an image through nozzles in repeated horizontal movements. Accordingly, when a pattern shaped like a worm (‘worm’ pattern) occurs in a diagonal direction in a binary output image, a ‘bending phenomenon’ occurs such that black dots are improperly printed as the position of the nozzles in each print unit changes in a horizontal direction.